package leetcode;

import java.util.HashSet;
import java.util.LinkedList;

public class Lc433 {

    public int minMutation(String startGene, String endGene, String[] bank) {
        if (startGene.equals(endGene)) return 0;
        String[] ch = {"A", "G", "C", "T"};
        HashSet<String> bankSet = new HashSet<>();
        for (int i = 0; i < bank.length; i++) {
            bankSet.add(bank[i]);
        }
        if (!bankSet.contains(endGene))
            return -1;

        int step = 0;
        LinkedList<String> queue = new LinkedList<>();
        queue.offer(startGene);
        HashSet<String> visited = new HashSet<>();
        visited.add(startGene);
        while (!queue.isEmpty()) {
            int sz = queue.size();
            step ++;
            while (sz -- > 0) {
                String curGene = queue.poll();
                if (curGene.equals(endGene)) return step;
                for (int i = 0; i < curGene.length(); i++) {
                    for (int j = 0; j < ch.length; j++) {
                        if (!curGene.substring(i, i + 1).equals(ch[j])) {
                            String newGene = curGene.substring(0, i) + ch[j] ;
                            if (i != curGene.length()) newGene += curGene.substring(i + 1, curGene.length());
                            if (bankSet.contains(newGene) && !visited.contains(newGene)) {
                                if (newGene.equals(endGene)) return step;
                                queue.offer(newGene);
                                visited.add(newGene);
                            }
                        }
                    }
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
//        String s = "123";
//        String t = s.substring(0, 0);
////        String t1 = s.substring(3, 4);
//        String t2 = s.substring(2, 3);
//        System.out.println();


        String s = "AACCGGTT";
        String e = "AACCGGTA";
        String[] bank = {"AACCGGTA"};
        Lc433 lc433 = new Lc433();
        System.out.println(lc433.minMutation(s, e, bank));
    }



}
